#include<iostream>
#include<utility>
using namespace std;

template<class K,class E>
struct treeNode
{
    //关键字为K类型，值为E类型的数对
    std::pair<K,E> pair;
    treeNode*leftChild;
    treeNode*rightChild;
    treeNode(){
        leftChild=rightChild=nullptr;
    };
    treeNode(std::pair<K,E>&p){
        this->pair=p;
        leftChild=rightChild=nullptr;
    }
};

//二叉搜索树，注意并不是平衡的
template<class K,class E>
class BinarySearchTree{
private:
    int treeSize;
    treeNode<K,E>*root;
    
    void visit(treeNode<K,E>*node)const{
        if(node==nullptr)
            cout<<"The node is nullptr"<<endl;
        else
            cout<<"Key: "<<node->pair.first<<" Element: "<<node->pair.second<<endl;
    }
    void dispose(treeNode<K,E>*node){
        if(node!=nullptr)
            delete node;
    }
public:
    BinarySearchTree(){
        treeSize=0;
        root=nullptr;
    };
    ~BinarySearchTree();

    std::pair<K,E>&find(K&key)const;
    treeNode<K,E>*& getRoot(){
        return root;
    }
    void insert(std::pair<K,E>&p);
    void erase(K&key);
    void ascendOutput(treeNode<K,E>*node)const;//按关键字升序输出所有数对
};

template<class K,class E>
BinarySearchTree<K,E>::~BinarySearchTree(){
    //后序遍历析构
    treeNode<K,E>*ptr=this->root;
    if(ptr!=nullptr){
        dispose(ptr->leftChild);
        dispose(ptr->rightChild);
        dispose(ptr);
    }
}

template<class K,class E>
std::pair<K,E>& BinarySearchTree<K,E>::find(K&key)const{
    treeNode<K,E>*ptr=this->root;
    //根据关键字大小下降查找即可
    //未寻找到则返回NULL
    while(ptr!=nullptr){
        if(key<ptr->pair.first)
            ptr=ptr->leftChild;
        else if(key>ptr->pair.first)
            ptr=ptr->rightChild;
        else
            return &ptr->pair;
    }
    return NULL;
}

template<class K,class E>
void BinarySearchTree<K,E>::insert(std::pair<K,E>&p){
    //1.查找关键字为p.first的数对
    //2.若存在此关键字，则更新element值
    //3.若不存在，则将此数对作为搜索中断节点的孩子插入树中
    treeNode<K,E>*pre,*ptr=this->root;
    while(ptr!=nullptr){
        pre=ptr;
        if(p.first<ptr->pair.first)
            ptr=ptr->leftChild;
        else if(p.first>ptr->pair.first)
            ptr=ptr->rightChild;
        else{
            //查找到此关键字，更新element值
            ptr->pair.second=p.second;
            return;
        }
    }
    //未查找到此关键字，则作为中断节点的孩子插入树中
    if(this->root!=nullptr){
        if(p.first<pre->pair.first)
            pre->leftChild=new treeNode<K,E>(p);
        else
            pre->rightChild=new treeNode<K,E>(p);
    }
    else
        this->root=new treeNode<K,E>(p);
    this->treeSize++;
}

template<class K,class E>
void BinarySearchTree<K,E>::erase(K&key){
    //考虑两种情况：
    //1.删除节点有一棵非空子树或没有子树
    //2.删除节点有两棵非空子树
    treeNode<K,E>*pre=nullptr,*ptr=this->root;
    //查找关键字为key的节点
    while (ptr!=nullptr&&ptr->pair.first!=key)
    {
        pre=ptr;
        if(key<ptr->pair.first)
            ptr=ptr->leftChild;
        else if(key>ptr->pair.first)
            ptr=ptr->rightChild;
    }

    if(ptr==nullptr){
        cout<<"No such key node."<<endl;
        return;
    }

    if(ptr->leftChild!=nullptr && ptr->rightChild!=nullptr){
        //情况3，教材给出的思路难以理解，这里采用更为常见的思路
        //寻找左子树最大节点
        treeNode<K,E>*leftMax=ptr->leftChild;
        treeNode<K,E>*leftMaxParent=ptr;

        while(leftMax->rightChild!=nullptr){
            leftMaxParent=leftMax;
            leftMax=leftMax->rightChild;
        }

        //此时，无需关注过多细节，只需要考虑两种情况：
        //1.leftMax是其父节点的左孩子
        //2.leftMax是其父节点的右孩子
        //注意，leftMax的右孩子必为nullptr
        ptr->pair=leftMax->pair;
        if(leftMax==leftMaxParent->leftChild)
            leftMaxParent->leftChild=leftMax->leftChild;
        else if(leftMax==leftMaxParent->rightChild)
            leftMaxParent->rightChild=leftMax->leftChild;
        delete leftMax;
    }
    else{
        //情况1、2
        //获取ptr可能存在的孩子指针
        treeNode<K,E>*child;
        if(ptr->leftChild!=nullptr)
            child=ptr->leftChild;
        else
            child=ptr->rightChild;

        if(ptr==root)
            root=child;
        else if(ptr==pre->leftChild)
            pre->leftChild=child;
        else if(ptr==pre->rightChild)
            pre->rightChild=child;

        delete ptr;
    }
    treeSize--;
}

template<class K,class E>
void BinarySearchTree<K,E>::ascendOutput(treeNode<K,E>*node)const{
    //按升序输出数对
    //对于一个非叶节点而言，关键字大小为：左<中<右，升序输出采取中序遍历
    if(node!=nullptr){
        ascendOutput(node->leftChild);
        visit(node);
        ascendOutput(node->rightChild);
    }
}

int main(){
    BinarySearchTree<int,int>tree;
    std::pair<int,int>*p=new std::pair<int,int>;
    
    p->first=1;
    p->second=22;
    tree.insert(*p);

    p->first=4;
    p->second=76;
    tree.insert(*p);

    p->first=12;
    p->second=31;
    tree.insert(*p);

    p->first=9;
    p->second=83;
    tree.insert(*p);

    p->first=10;
    p->second=55;
    tree.insert(*p);

    p->first=-1;
    p->second=26;
    tree.insert(*p);

    p->first=6;
    p->second=61;
    tree.insert(*p);

    p->first=5;
    p->second=51;
    tree.insert(*p);

    tree.ascendOutput(tree.getRoot());
    int a=9;
    tree.erase(a);
    cout<<endl<<"After erasing 9:"<<endl;
    tree.ascendOutput(tree.getRoot());
    
    int b=1;
    tree.erase(b);
    cout<<endl<<"After erasing 1:"<<endl;
    tree.ascendOutput(tree.getRoot());

    delete p;
    return 0;
}